package com.algorithm.tuling.zhaoyun.t02.arr;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.io.UnsupportedEncodingException;

import javax.imageio.stream.FileImageInputStream;

/**
 面试经典：
 给你一个文件里面包含全国人民（14亿）的年龄数据（0~180），现在要你统计每一个年龄有多少人？
 给定机器为 单台+2CPU+2G内存。不得使用现成的容器，比如map等。
 数组算法
 在以上情况下你该如何以最高效的方法来解决这个问题？
 排序算法：1 1 1 2 2 2  3 3 3 4 4 5。想过没？能不能解决这个问题？：不能 为什么？
 排序的最高效算法：O(nlogn) 14亿，排不出来，而且内存也不够。
 int a[] = new int[180];a[0]++;0表示的是0岁，a[0]的值表示的就是0有多少人.
 12：56
 23：56111
 52：9999888
 下标：数组最优一个特点。这里可以通下标表示成有意义的数据，不只是数据里面的标记，年龄和下标对应。随机访问：可以直接通过下标定位到数组中的某一个数据


 */
public class AgeStas {

	public static void main(String[] args) throws Exception {
		String str = null;
		String fileName = "D:\\tmp\\algorithm\\age1.txt";
		InputStreamReader isr = new InputStreamReader(new FileInputStream(fileName),"UTF-8");
		
		long start = System.currentTimeMillis();
		BufferedReader br = new BufferedReader(isr);
		int tot = 0 ;	//21亿
		int data [] = new int[200];
		while((str = br.readLine()) != null){		//一行一行的读 O(n)
			int age = Integer.valueOf(str);
			data[age] ++ ;
			tot ++ ;
		}
		//O(n) 14亿. 100万/秒 *1000 = 10亿 100~1000s之间 => 500s以下 60*8=480s
		System.out.println("总共的数据大小: " + tot);
		
		for(int i = 0 ; i < 200 ; i ++){//下标从0开始的
			System.out.println(i + ":" + data[i]);
		}
		//144239ms => 144s
		//291645ms
		System.out.println("计算花费的时间为:" + (System.currentTimeMillis() - start) + "ms");
	}
}
